package 力扣._00周赛._429周赛.问题2;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        Set<Integer> set = new HashSet<>();
        int[] t = new int[n];
        for(int i=0,j=n-1;i<=j;i++,j--){
            if(i==j){
                if(i>0){
                    int l = Math.max(t[i-1]+1, nums[i]-k);
                    int r = Math.min(t[j+1]-1, nums[j]+k);
                    if(l<=r){
                        set.add(l);
                        t[i] = l;
                    }
                }else {
                    set.add(nums[i]);
                }
                break;
            }
            // 左边减
            int l;
            if(i==0) {
                l = nums[i] - k;
            }else{
                l = Math.max(t[i-1]+1, nums[i]-k);
            }
            for(;l<=nums[i];l++){
                if(!set.contains(l)){
                    set.add(l);
                    t[i] = l;
                    break;
                }
            }
            // 右边加
            int r;
            if(j==n-1) {
                r = nums[j] + k;
            }else{
                r = Math.min(t[j+1], nums[j]+k);
            }
            for(;r>=nums[j];r--){
                if(!set.contains(r)){
                    set.add(r);
                    t[j] = r;
                    break;
                }
            }
        }
        System.out.println(Arrays.toString(t));
        return set.size();
    }

    public static void main(String[] args) {
        Solution s = new Solution();
//        int[] nums = new int[100000];
//        int k = 1000000000;
        // [6,7,6,6,7]
        //1©leetcode
        int[] nums = {7,10,10,8,9};
        int k = 0;
        System.out.println(s.maxDistinctElements(nums, k));
    }
}